#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int search(int* nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize - 1;
    int middle = (left + right) / 2;
    if (nums[left] == target)
    {
        return left;
    }
    if (nums[right] == target)
    {
        return right;
    }
    if (nums[left] < nums[middle]
        && nums[middle] < nums[right])
    {
        while (left < right)
        {
            if (nums[middle] < target)
            {
                left = middle + 1;
                middle = (left + right) / 2;
            }
            if (nums[middle] > target)
            {
                right = middle - 1;
                middle = (left + right) / 2;
            }
            if (nums[middle] == target)
            {
                return middle;
            }
        }
    }
    else
    {
        left = 0;
        right = numsSize - 1;
        middle = (left + right) / 2;
        while (left < right)
        {
            if (nums[middle] < nums[left])
            {
                right = middle;
                middle = (left + right) / 2;
            }
            if (nums[middle] > nums[right])
            {
                left = middle;
                middle = (left + right) / 2;
            }
            if (nums[middle] == nums[left])
            {
                break;
            }
        }
        if (nums[middle] > nums[right])
        {
            int left1 = 0;
            int right1 = middle;
            int middle1 = (left1 + right1) / 2;
            int left2 = middle + 1;
            int right2 = numsSize - 1;
            int middle2 = (left2 + right2) / 2;
            while (left1 < right1)
            {
                if (nums[middle1] < target)
                {
                    left1 = middle1 + 1;
                    middle1 = (left1 + right1) / 2;
                }
                if (nums[middle1] > target)
                {
                    right1 = middle1 - 1;
                    middle1 = (left1 + right1) / 2;
                }
                if (nums[middle1] == target)
                {
                    return middle1;
                }
            }
            while (left2 < right2)
            {
                if (nums[middle2] < target)
                {
                    left2 = middle2 + 1;
                    middle2 = (left2 + right2) / 2;
                }
                if (nums[middle2] > target)
                {
                    right2 = middle2 - 1;
                    middle2 = (left2 + right2) / 2;
                }
                if (nums[middle2] == target)
                {
                    return middle2;
                }
            }
        }
        if (nums[middle] < nums[left])
        {
            int left1 = 0;
            int right1 = middle - 1;
            int middle1 = (left1 + right1) / 2;
            int left2 = middle;
            int right2 = numsSize - 1;
            int middle2 = (left2 + right2) / 2;
            while (left2 < right2)
            {
                if (nums[middle2] < target)
                {
                    left2 = middle2 + 1;
                    middle2 = (left2 + right2) / 2;
                }
                if (nums[middle2] > target)
                {
                    right2 = middle2 - 1;
                    middle2 = (left2 + right2) / 2;
                }
                if (nums[middle2] == target)
                {
                    return middle2;
                }
            }
            while (left1 < right1)
            {
                if (nums[middle1] < target)
                {
                    left1 = middle1 + 1;
                    middle1 = (left1 + right1) / 2;
                }
                if (nums[middle1] > target)
                {
                    right1 = middle1 - 1;
                    middle1 = (left1 + right1) / 2;
                }
                if (nums[middle1] == target)
                {
                    return middle1;
                }
            }
        }
    }
    return -1;
}
int main()
{
    int a[3] = { 1,3,5 };
    int sz = sizeof(a) / 4;
    search(a, sz, 0);
    return 0;
}